/*
 * =====================================================================================
 *
 *       Filename:  mergeSortLargeTest.cpp
 *
 *    Description:  归并算法测试
 *
 *        Version:  1.0
 *        Created:  2011-10-31 15:02:34
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  YOUR NAME (), 
 *        Company:  
 *
 * =====================================================================================
 */

#include "SortProblem.h"
#include <ctime>
#include <iostream>

#define LARGE_COUNT 10000000

int main(int argc, char *argv[]) {
    std::cout << "the max random count is " << LARGE_COUNT << std::endl;
    clock_t start, finish;

    //////////////////////////////////////////////////////////////////////
    std::cout << "merge sort using mergeOrigin." << std::endl;    
    {
        std::vector<int> A;
        genRandVector(A, LARGE_COUNT);

        start = clock();
        mergeSort(A, 0, (int)A.size()-1, &mergeOrigin);
        finish = clock();
        std::cout << "mergeSort running time is "
            << (finish - start) / CLOCKS_PER_SEC
            << " seconds"
            << std::endl;
    }
    {
        std::vector<int> A;
        genRandVector(A, LARGE_COUNT);

        start = clock();
        mergeSortWithInsert(A, 0, (int)A.size()-1, &mergeOrigin);
        finish = clock();
        std::cout << "mergeSortWithInsert running time is "
            << (finish - start) / CLOCKS_PER_SEC
            << " seconds"
            << std::endl;
    }
    {
        std::vector<int> A;
        genRandVector(A, LARGE_COUNT);

        start = clock();
        mergeSortLoop(A, 0, (int)A.size()-1, &mergeOrigin);
        finish = clock();
        std::cout << "mergeSortLoop running time is "
            << (finish - start) / CLOCKS_PER_SEC
            << " seconds"
            << std::endl;
    }
    {
        std::vector<int> A;
        genRandVector(A, LARGE_COUNT);

        start = clock();
        mergeSortLoopWithInsert(A, 0, (int)A.size()-1, &mergeOrigin);
        finish = clock();
        std::cout << "mergeSortLoopInsert running time is "
            << (finish - start) / CLOCKS_PER_SEC
            << " seconds"
            << std::endl;
    }

    //////////////////////////////////////////////////////////////////////
    std::cout << "merge sort using mergeUseMax." << std::endl;    
    {
        std::vector<int> A;
        genRandVector(A, LARGE_COUNT);

        start = clock();
        mergeSort(A, 0, (int)A.size()-1, &mergeUseMax);
        finish = clock();
        std::cout << "mergeSort running time is "
            << (finish - start) / CLOCKS_PER_SEC
            << " seconds"
            << std::endl;
    }
    {
        std::vector<int> A;
        genRandVector(A, LARGE_COUNT);

        start = clock();
        mergeSortWithInsert(A, 0, (int)A.size()-1, &mergeUseMax);
        finish = clock();
        std::cout << "mergeSortWithInsert running time is "
            << (finish - start) / CLOCKS_PER_SEC
            << " seconds"
            << std::endl;
    }
    {
        std::vector<int> A;
        genRandVector(A, LARGE_COUNT);

        start = clock();
        mergeSortLoop(A, 0, (int)A.size()-1, &mergeUseMax);
        finish = clock();
        std::cout << "mergeSortLoop running time is "
            << (finish - start) / CLOCKS_PER_SEC
            << " seconds"
            << std::endl;
    }
    {
        std::vector<int> A;
        genRandVector(A, LARGE_COUNT);

        start = clock();
        mergeSortLoopWithInsert(A, 0, (int)A.size()-1, &mergeUseMax);
        finish = clock();
        std::cout << "mergeSortLoopInsert running time is "
            << (finish - start) / CLOCKS_PER_SEC
            << " seconds"
            << std::endl;
    }
    
    //////////////////////////////////////////////////////////////////////
    std::cout << "merge sort using mergeExpand." << std::endl;    
    {
        std::vector<int> A;
        genRandVector(A, LARGE_COUNT);

        start = clock();
        mergeSort(A, 0, (int)A.size()-1, &mergeExpand);
        finish = clock();
        std::cout << "mergeSort running time is "
            << (finish - start) / CLOCKS_PER_SEC
            << " seconds"
            << std::endl;
    }
    {
        std::vector<int> A;
        genRandVector(A, LARGE_COUNT);

        start = clock();
        mergeSortWithInsert(A, 0, (int)A.size()-1, &mergeExpand);
        finish = clock();
        std::cout << "mergeSortWithInsert running time is "
            << (finish - start) / CLOCKS_PER_SEC
            << " seconds"
            << std::endl;
    }
    {
        std::vector<int> A;
        genRandVector(A, LARGE_COUNT);

        start = clock();
        mergeSortLoop(A, 0, (int)A.size()-1, &mergeExpand);
        finish = clock();
        std::cout << "mergeSortLoop running time is "
            << (finish - start) / CLOCKS_PER_SEC
            << " seconds"
            << std::endl;
    }
    {
        std::vector<int> A;
        genRandVector(A, LARGE_COUNT);

        start = clock();
        mergeSortLoopWithInsert(A, 0, (int)A.size()-1, &mergeExpand);
        finish = clock();
        std::cout << "mergeSortLoopInsert running time is "
            << (finish - start) / CLOCKS_PER_SEC
            << " seconds"
            << std::endl;
    }
    //////////////////////////////////////////////////////////////////
    std::cout << "merge sort with copy." << std::endl;
    {
        std::vector<int> A;
        genRandVector(A, LARGE_COUNT);

        start = clock();
        mergeSortWithCopy(A, 0, (int)A.size()-1);
        finish = clock();
        std::cout << "mergeSortWithCopy running time is "
            << (finish - start) / CLOCKS_PER_SEC
            << " seconds"
            << std::endl;
    }
    {
        std::vector<int> A;
        genRandVector(A, LARGE_COUNT);

        start = clock();
        mergeSortWithCopyInsert(A, 0, (int)A.size()-1);
        finish = clock();
        std::cout << "mergeSortWithCopyInsert running time is "
            << (finish - start) / CLOCKS_PER_SEC
            << " seconds"
            << std::endl;
    }
}


